Schnorr 署名びりあるさん
この記事を自分なりに解釈したメモ
$ e = H(m;g^{y} p^{e})
出力である e が入力にもなっているため、これを満たすような y,e を見つけるのは難しい
ただしある値を知っていると簡単。その値を秘密鍵として使うことができる。
このとき 公開鍵 p は秘密鍵 s を用いて
$ p=g^{s}
と表せると
$ H(m;g^{y} (g^{s})^{e}) = H(m;g^{y+se})
である。
ちなみに e は exam から来ている
この表現のなにが嬉しいかというと
任意の r から、 $ e = H(m;g^{r})と e を決めることができる
また、$ r = y + se であるから、$ y = r - se となる
このように y と e を定めることができるため、前述の y,e を見つけるのが難しい、という問題を解消している。
y と e が独立した変数だったが、r という変数にまとめることができたからだと思う。
つまり、秘密鍵 s を知っていれば y,e は簡単に求めることができる。したがって y,e が 秘密鍵 s の署名として機能する。
s を知っていれば、任意の e に対して y,e のペアを簡単に求めることができる。
y を s, r を k, s を dと表記し以下のように表している説明も多い
$ s = k - de
また e を置き換えて $ s = k + H(m; kG)d のように表記する場合もある
個人認証アルゴリズムの話
読み取り機側からランダムに与えられる e との間に、$ g^{r} = g^{y}p^{e} の関係が成り立つような $ x =g^{r} を事前に求めることはできない。y は $ y=r-se なので、r,e が決まっている状況では、$ g^{s} = p が成立する s を求めることができるということは、秘密鍵を任意に求められることに等しいため。
別の言い方
$ yG = rG + esG のときに、s を知らずに$ y = r + se となるような y を求められるか？
これは P の秘密鍵を求めているのと同じなので s はわからない
yG からは y はわらかない
ステップ 1 とステップ 2 の順番を入れ替えることを考える とある
逆に e が与えられているとすると、任意の x について成立する $ y=r-se を計算できてしまう
したがって e はあとからランダムに与えられる必要があるが、仮に e が与えられたとしても、$ x = g^{r} をあとから変更できなければ問題はないとも言える
なので、e を x にコミットしておけばよい。例えば $ e = Hash(x)のように。こうすることで、e に対して x は任意の値ではだめになる。
こうすることで、アルゴリズム3’（双方向通信の必要ない Schnorr 個人認証方式） が成立する
楕円曲線
$ e = H(m;yG + eP)